//todo: LeetCode692. 前K个高频单词

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> recordMap; //记录每一个单词出现的次数，并按单词的字典顺序为单词排序
        for (auto& word : words) {
            ++recordMap[word];
        }

        multimap<int, string, greater<int>> sortMap; //multimap允许key值相同
        //按照单词出现的次数，从大到小为单词排序
        //因为map的性质，导致其自带排序功能，并且该排序具有稳定性，即在排序时不会打乱数据的顺序
        //在该情况下，数据的顺序为数据入multimap的顺序，所以sortMap最后排序出来的结果就是题目要求的结果
        for (auto& pr : recordMap) { // auto == pair<string, int>
            sortMap.insert(make_pair(pr.second, pr.first));
        }

        vector<string> ret;
        multimap<int, string, greater<int>>::iterator bit = sortMap.begin();
        while(k--) {
            ret.push_back(bit->second);
            ++bit;
        }

        return ret;
    }
};